package algorithm;

import com.sun.org.apache.xpath.internal.objects.XString;

/**
 * 最长公共前缀
 */
public class LeetCode_longestCommonPrefix_14 {
    /**
     * 横向臊扫描
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        String res = strs[0];
        for (int i = 1; i < strs.length; i++) {
//            StringBuffer sb = new StringBuffer();
//            // 获取两个需要比较的两个字符串长度较小的值
//            int size = Math.min(res.length(), strs[i].length());
//            for (int j = 0; j < size; j++) {
//                if (res.charAt(j) == strs[i].charAt(j)) {
//                    sb.append(res.charAt(j));
//                } else {
//                    break;
//                }
//            }
//            res = sb.toString();
            res = longestCommonPrefix(res, strs[i]);

        }
        return res;
    }

    public String longestCommonPrefix(String res, String str) {
        int size = Math.min(res.length(), str.length());
        int index = 0;
        while (index < size && res.charAt(index) == str.charAt(index)) {
            index++;
        }
        return res.substring(0, index);
    }

    /**
     * 纵向扫描
     */
    public String longestCommonPrefix(String[] strs, boolean noUsed) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        int count = strs[0].length();
        int len = strs.length;
        for (int i = 0; i < count; i++) {
            char c = strs[i].charAt(i);
            for (int j = 0; j < len; j++) {
                if (i == strs[j].length() || strs[j].charAt(j) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    public String longestCommonPrefix(String[] strs, int noUsed) {
        if (strs.length == 0 || strs == null) {
            return"";
        }
        return longestCommonPrefix(strs, 0, strs.length - 1);

    }
    public String longestCommonPrefix(String[] strs, int start, int end) {
        if (start == end) {
            return strs[start];
        }else {
            int mid = start + (end - start) / 2;
            String left = longestCommonPrefix(strs, start, mid);
            String right = longestCommonPrefix(strs, mid + 1, end);
            return commonPrefix(left, right);
        }
    }

    public String commonPrefix(String left, String right) {
        int size = Math.min(left.length(), right.length());
        int index = 0;
        while (index < size && left.charAt(index) == right.charAt(index)) {
            index++;
        }
        return left.substring(0, index);
    }

}
